package Algorithms.KMP_05;

/*
 * @Author 罗
 * @date 2020/3/30 - 12:19 上午
 *
 */

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class KMP {
    /**
     * kmp算法最终版4.0
     * @param origin
     * @param key
     * @return
     */
    public static int kmp4(String origin, String key) {
        int[] table = getTable3(key);
        for (int i = 0, j = 0; i < origin.length(); i++) {
            while (j > 0 && origin.charAt(i) != key.charAt(j)) {
                j = table[j - 1];
            }
            if (origin.charAt(i) == key.charAt(j)) {
                j++;
            }
            if (j == key.length()) {
                /*
                 * 因为返回的时候i还没有+1，所以要+1了之后再返回，才能消除误差
                 * 此时，i为匹配字符串的终点-1，j为匹配字符串的长度
                 * */
                return i - j + 1;
            }
        }


        return -1;
    }


    @Deprecated
    public static int kmp3(String origin, String key) {
        int[] table = getTable3(key);
        System.out.println(Arrays.toString(table));
        char[] c1 = origin.toCharArray();
        char[] c2 = key.toCharArray();
        int i = 0;
        int record = 0;
        int j = 0;
        while (i < c1.length && j < c2.length) {
            if (c1[i] == c2[j]) {
                j++;
                i++;
                if (j == c2.length) {
                    return record;
                }
            } else {
                if (j > 0) {
                    i = record + j - table[j - 1];
                } else {
                    i++;
                }
                record = i;
                j = 0;
            }
        }
        return -1;
    }

    /**
     * 最优的获取部分匹配表的算法
     *
     * @param key
     * @return
     */
    private static int[] getTable3(String key) {
        int[] table = new int[key.length()];
        /*
         * 因为table[0] 对应的只有一个元素，无法形成前缀或者后缀
         * 所以不用进行遍历i直接从1开始
         * */
        table[0] = 0;
        for (int i = 1, j = 0; i < key.length(); i++) {

            /*
             * 避免之后出现不相同的元素，依然会使得j++
             * Kmp算法的核心，不懂的话，debug一遍就行，不好描述
             * key.charAt(i) != key.charAt(j) 两者不等的时候，就在这里将j置0
             * */
            while (j > 0 && key.charAt(i) != key.charAt(j)) {
                j = table[j - 1];
            }
            if (key.charAt(i) == key.charAt(j)) {
                j++;
            }
            table[i] = j;
        }
        return table;
    }

    /**
     * kmp算法2.0
     *
     * @param origin
     * @param key
     * @return
     */
    @Deprecated
    public static int kmp2(String origin, String key) {
        char[] c1 = origin.toCharArray();
        char[] c2 = key.toCharArray();
        int[] value = getTable2(c2);
        /*
         * c2和value[]形成部分匹配表
         * */
        int i = 0;
        int j = 0;
        int record = 0;
        while (i < c1.length && j < c2.length) {
            if (c1[i] == c2[j]) {
                i++;
                j++;
                if (j == c2.length) {
                    return record;
                }
            } else {
                if (j != 0) {
                    i = record + j - value[j - 1];
                } else {
                    i++;
                }
                record = i;
                j = 0;
            }
        }
        return -1;
    }

    /**
     * 获取部分匹配表
     * 比较容易看懂的版本
     *
     * @param key
     * @return
     */
    @Deprecated
    private static int[] getTable2(char[] key) {
        int result = 0;
        int[] table = new int[key.length];
        /*
         * 因为前缀不包含key的最后一个字符，所以长度-1
         * 二维数组存放元素的组合
         * 一维数组存放具体的元素排放
         * */
        char[][] prefix = new char[key.length - 1][];
        /*
         * 将每一种前缀的情况放入二维数组
         * */
        for (int i = 0; i < prefix.length; i++) {
            /*
             * String(char[],start,end)构造器含头，不含尾，所以构造器的end要+1
             * */
            prefix[i] = new String(key, 0, i + 1).toCharArray();
        }
        System.out.println(Arrays.deepToString(prefix));
        char[] prefixTemp;
        char[] suffixTemp;
        /*
         * 后缀的长度越来越短
         * */
        for (int suffixLength = key.length - 1; suffixLength > 1; suffixLength--) {
            /*
             * 后缀的前指针一直往后移动
             * 用于辅助缩短后缀的长度
             * */
            for (int i = 1; i <= suffixLength; i++) {

                prefixTemp = prefix[suffixLength - i];
                suffixTemp = new String(key, i, suffixLength - i + 1).toCharArray();

                if (Arrays.equals(prefixTemp, suffixTemp)) {
                    result = suffixTemp.length;
                    break;
                }
            }
            if (result > 0) {
                table[suffixLength] = result;
                result = 0;
            } else {
                table[suffixLength] = result;
            }
        }

        System.out.println(Arrays.toString(table));
//        for (int suffixEnd = 2; suffixEnd < key.length; suffixEnd++) {

        //for (int i = suffixEnd; i < key.length; i++) {
        /*
         * 从前缀数组集合中找出长度与后缀匹配的
         * 后缀的长度从最长开始递减，而前缀数组从1开始递增
         * 为了匹配长度，在后缀递减的同时，要使得前缀递增
         * 前缀数组递减 --> prefix.length - i
         * */
//                System.out.println(Arrays.toString(prefix[suffixEnd-2]));
//                System.out.println(Arrays.toString(new String(key, 1, suffixEnd-1).toCharArray()) + "-->后缀");
/*            for (int j = prefix.length - i; j > 0; j--) {
                System.out.println(Arrays.toString(prefix[j])+"-------------");
                if (new String(key, 1, i).toCharArray().equals(prefix[prefix.length - i])) {

                }
            }*/
        //}
//            System.out.println("---------------------");
//        }
        return table;
    }

    /**
     * 自己写的kmp算法
     *
     * @param origin
     * @param key
     * @return
     */
    @Deprecated
    public static int kmp(String origin, String key) {
        Map<String, Integer> table = getTable(key);
        for (Map.Entry<String, Integer> entry : table.entrySet()) {
            System.out.println(entry.getKey() + "\t" + entry.getValue());
        }
        char[] c1 = origin.toCharArray();
        char[] c2 = key.toCharArray();
        /*
         * 指向要截取字符串的尾部
         * */
        int i = 0;
        int j = 0;
        /*
         * 指向要截取字符串的头部
         * */
        int record = 0;
        String temp;
        int length = 0;
        while (i < c1.length && j < c2.length) {
            if (c1[i] == c2[j]) {
                i++;
                j++;
                /*
                 * 指向c2的指针j指到了c2的最后
                 * 说明该关键字已经被找到
                 * */
                if (j == c2.length) {
                    /*
                     * record -> i 区间的子字符串已经和c2完全匹配
                     * 现在返回该子字符串的头部出现的位置record
                     * */
                    return record;
                }
            } else {
                /*
                 * 将c1[record] -> c2[i] 之间的char拼接为String
                 * 方便到HashMap中进行查找
                 * */
                temp = new String(c1, record, i - record);

                /*
                 * 因为上面的String()构造器，至少要在c1[i] == c2[j]匹配一个元素
                 *      record指针才不会后移，String()构造器才可以构造一个有长度的字符
                 *      而这个字符的顺序一定是和部分匹配表中元素的顺序是一样的
                 *      因此在部分匹配表中一定能够查询的到对应的value
                 *      而不会(Integer)null 异常
                 * 部分匹配表中的元素长度至少为1
                 * 若去
                 * */
                if (temp.length() > 0) {
                    length = temp.length();
                    /*
                     * kmp算法体现的地方
                     * */
                    i = record + length - table.get(temp);
                } else {
                    /*
                     * 如果没有匹配部分匹配表的任何项，则将i指针后移
                     * */
                    i++;
                }
                /*
                 * 更新record指针
                 * */
                record = i;
                /*
                 * 重新让j指向c1[0]
                 * */
                j = 0;
            }
        }


        return -1;
    }

    /**
     * 获得部分匹配表
     *
     * @return
     */
    private static Map<String, Integer> getTable(String key) {
        Map<String, Integer> table = new HashMap<>();
        char[] c = key.toCharArray();
        /*
         * 记录前缀的所有元素
         * */
        char[] prefix;
        /*
         * 记录后缀的所有元素
         * */
        char[] suffix;

        /*
         * 存放前缀的每一种可能的组合
         * */
        String[] temp;
        /*
         * 从temp[]中取出来的其中一种前缀
         * */
        String singlePrefix;
        /*
         * 存放后缀
         * */
        String singleSuffix;
        /*
         * 放入map中的key
         * */
        String mapKey;
        /*
         * 存放key对应的value
         * */
        int mapValue = 0;
        /*
         * 因为只有一个元素的话无法构成前缀或者后缀（至少需要两个元素才能构成）
         * 所以单独挑出来添加
         * */
        table.put(new String(c, 0, 1), 0);
        /*
         * 连个元素以上的情况，每一种情况都有前缀或者后缀
         * <=是为了subString()方法不含尾，所以可以使用=
         * */
        for (int i = 2; i <= c.length; i++) {
            /*
             * 因为前缀prefix不包含第一个元素，后缀suffix不包含最后一个元素
             * 但是要包含前后缀所有元素作为mapKey
             * */
            mapKey = new String(c, 0, i);
            /*
             * 获取前缀的元素，从第0个到倒数第二个区间为前缀
             * subString()不包含尾部
             * */
            prefix = key.substring(0, i - 1).toCharArray();
            /*
             * 创建temp[]用于存放之后组合好的前缀
             * 因为前缀是顺序附加到上一个元素的后面，所以前缀元素组成的个数为 i-1
             * */
            temp = new String[i - 1];
            for (int j = 0; j < prefix.length; j++) {
                /*
                 * 将前缀元素组成为前缀，然后放入前缀数组
                 * */
                temp[j] = new String(prefix, 0, j + 1);
            }
            /*
             * 获取后缀元素，除了第0个元素都是后缀元素
             * 不包含i
             * */
            suffix = key.substring(1, i).toCharArray();
            /*
             * 遍历后缀的元素
             * */
            for (int j = 0; j < suffix.length; j++) {
                /*
                 * 从前缀数组中取出前缀组合
                 * 这里拼接成的后缀元素是从长到短，但是前缀数组的下标顺序从小到大，对应的前缀组合长度是从短到长
                 * 因此在这里作出变换，使得前缀元素的长度和后缀元素的长度一致
                 * */
                singlePrefix = temp[temp.length - j - 1];
                /*
                 * 把后缀元素拼接为后缀组合
                 * 从长到短
                 * String(char[],offset,length)构造器，必须满足 offset+length <=char[].length
                 * */
                singleSuffix = new String(suffix, j, suffix.length - j);
                /*
                 * 判断相同长度的前缀和后缀是否一致
                 * */
                if (singlePrefix.contentEquals(singleSuffix)) {
                    /*
                     * 一致，记录下该mapKey对应的mapValue
                     * 前缀的内容.equals(后缀的内容) 时
                     * 前缀长度 = 后缀长度 = suffix.length - j
                     * */
                    mapValue = suffix.length - j;
                    /*
                     * 后缀长度递减，找到一个后缀组合，如果之后还有后缀组合，那么一定比现在的后缀组合短
                     * 所以提前退出
                     * */
                    break;
                }
            }
            if (mapValue > 0) {
                table.put(mapKey, mapValue);
                mapValue = 0;
            } else {
                table.put(mapKey, 0);
            }

        }
        return table;
    }

}
